package kyssion.leetcode.num1_50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1:
 * <p>
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * [1, 7],
 * [1, 2, 5],
 * [2, 6],
 * [1, 1, 6]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 * [1,2,2],
 * [5]
 * ]
 */
public class code40_组合总和II {
    public static void main(String[] args) {
        System.out.println(new code40_组合总和II().combinationSum2(
                new int[]{1,1
                },5
        ));
    }

    /**
     * 39 题目的变形,这个很简单就解决了
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Stack<Integer> stack = new Stack<>();
        Arrays.sort(candidates);
        List<List<Integer>> listList = new ArrayList<>();
        ans(candidates, stack, 0, target, listList);
        return listList;
    }

    public void ans(int[] items, Stack<Integer> stack, int index, int target, List<List<Integer>> all) {
        if (target == 0) {
            all.add(new ArrayList<>(stack));
            return;
        }
        for (int a = index; a < items.length; a++) {
            if(a!=index&&items[a]==items[a-1]){
                continue;
            }
            if (target - items[a] >= 0) {
                stack.push(items[a]);
                ans(items, stack, a + 1, target - items[a], all);
                stack.pop();
            }
        }
        return;
    }

    /**
     * 使用dp的方法进行优化
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2_2(int[] candidates, int target) {
        return new ArrayList<>();
    }
}

